package com.maltys.greedy;

import java.util.Arrays;
import java.util.Map;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/">K 次取反后最大化的数组和</a>
 */
public class MaxSumOfArrayAfterKNegations {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && k > 0 && nums[i] < 0; i++) {
            nums[i] = -nums[i];
            k--;
        }
        if (k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

    public static void main(String[] args) {
        MaxSumOfArrayAfterKNegations negations = new MaxSumOfArrayAfterKNegations();
        int maxSum = negations.largestSumAfterKNegations(new int[]{-5, -4, -3, -2, -1}, 5);
        System.out.println(maxSum);
    }
}
